<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    1040. Maximum Binary Tree II
   </h1>
   <p>
    We are given the
    <code>
     root
    </code>
    &nbsp;node of a
    <em>
     maximum tree:
    </em>
    a tree where every node has a value greater than any other value in its subtree.
   </p>
   <p>
    Just as in the
    <a href="https://leetcode.com/problems/maximum-binary-tree/">
     previous problem
    </a>
    , the given tree&nbsp;was constructed from an list&nbsp;
    <code>
     A
    </code>
    &nbsp;(
    <code>
     root = Construct(A)
    </code>
    ) recursively with the following&nbsp;
    <code>
     Construct(A)
    </code>
    routine:
   </p>
   <ul>
    <li>
     If
     <code>
      A
     </code>
     is empty, return
     <code>
      null
     </code>
     .
    </li>
    <li>
     Otherwise, let
     <code>
      A[i]
     </code>
     be the largest element of
     <code>
      A
     </code>
     .&nbsp; Create a
     <code>
      root
     </code>
     node with value
     <code>
      A[i]
     </code>
     .
    </li>
    <li>
     The left child of
     <code>
      root
     </code>
     will be
     <code>
      Construct([A[0], A[1], ..., A[i-1]])
     </code>
    </li>
    <li>
     The right child of
     <code>
      root
     </code>
     &nbsp;will be
     <code>
      Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
     </code>
    </li>
    <li>
     Return
     <code>
      root
     </code>
     .
    </li>
   </ul>
   <p>
    Note that we were not given A directly, only a root node
    <code>
     root = Construct(A)
    </code>
    .
   </p>
   <p>
    Suppose
    <code>
     B
    </code>
    is a copy of
    <code>
     A
    </code>
    with the value
    <code>
     val
    </code>
    appended to it.&nbsp; It is guaranteed that
    <code>
     B
    </code>
    has unique values.
   </p>
   <p>
    Return
    <code>
     Construct(B)
    </code>
    .
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <p>
    <strong>
     <img alt="" src="https://assets.leetcode.com/uploads/2019/02/21/maximum-binary-tree-1-1.png" style="width: 159px; height: 160px;">
     <img alt="" src="https://assets.leetcode.com/uploads/2019/02/21/maximum-binary-tree-1-2.png" style="width: 169px; height: 160px;">
    </strong>
   </p>
   <pre>
<strong>Input: </strong>root = <span id="example-input-1-1">[4,1,3,null,null,2]</span>, val = <span id="example-input-1-2">5</span>
<strong>Output: </strong><span id="example-output-1">[5,4,null,1,3,null,null,2]
<strong>Explanation:</strong> A = </span><span>[1,4,2,3], B = </span><span>[1,4,2,3,5]</span>
</pre>
   <div>
    <p>
     <strong>
      Example 2:
      <br>
      <img alt="" src="https://assets.leetcode.com/uploads/2019/02/21/maximum-binary-tree-2-1.png" style="width: 180px; height: 160px;">
      <img alt="" src="https://assets.leetcode.com/uploads/2019/02/21/maximum-binary-tree-2-2.png" style="width: 214px; height: 160px;">
     </strong>
    </p>
    <pre>
<strong>Input: </strong>root = <span id="example-input-2-1">[5,2,4,null,1]</span>, val = <span id="example-input-2-2">3</span>
<strong>Output: </strong><span id="example-output-2">[5,2,4,null,1,null,3]
</span><span id="example-output-1"><strong>Explanation:</strong> A = </span><span>[2,1,5,4], B = </span><span>[2,1,5,4,3]</span>
</pre>
    <div>
     <p>
      <strong>
       Example 3:
       <br>
       <img alt="" src="https://assets.leetcode.com/uploads/2019/02/21/maximum-binary-tree-3-1.png" style="width: 180px; height: 160px;">
       <img alt="" src="https://assets.leetcode.com/uploads/2019/02/21/maximum-binary-tree-3-2.png" style="width: 201px; height: 160px;">
      </strong>
     </p>
     <pre>
<strong>Input: </strong>root = <span id="example-input-3-1">[5,2,3,null,1]</span>, val = <span id="example-input-3-2">4</span>
<strong>Output: </strong><span id="example-output-3">[5,2,4,null,1,3]
</span><span id="example-output-1"><strong>Explanation:</strong> A = </span><span>[2,1,5,3], B = </span><span>[2,1,5,3,4]</span>
</pre>
     <p>
      &nbsp;
     </p>
    </div>
   </div>
   <p>
    <strong>
     Note:
    </strong>
   </p>
   <ol>
    <li>
     <code>
      1 &lt;= B.length &lt;= 100
     </code>
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    1040. 最大二叉树 II
   </h1>
   <p>
    最大树定义：一个树，其中每个节点的值都大于其子树中的任何其他值。
   </p>
   <p>
    给出最大树的根节点
    <code>
     root
    </code>
    。
   </p>
   <p>
    就像
    <a href="https://leetcode-cn.com/problems/maximum-binary-tree/">
     之前的问题
    </a>
    那样，给定的树是从表&nbsp;
    <code>
     A
    </code>
    （
    <code>
     root = Construct(A)
    </code>
    ）递归地使用下述&nbsp;
    <code>
     Construct(A)
    </code>
    &nbsp;例程构造的：
   </p>
   <ul>
    <li>
     如果&nbsp;
     <code>
      A
     </code>
     &nbsp;为空，返回&nbsp;
     <code>
      null
     </code>
    </li>
    <li>
     否则，令&nbsp;
     <code>
      A[i]
     </code>
     &nbsp;作为 A 的最大元素。创建一个值为&nbsp;
     <code>
      A[i]
     </code>
     &nbsp;的根节点
     <code>
      root
     </code>
    </li>
    <li>
     <code>
      root
     </code>
     &nbsp;的左子树将被构建为&nbsp;
     <code>
      Construct([A[0], A[1], ..., A[i-1]])
     </code>
    </li>
    <li>
     <code>
      root
     </code>
     &nbsp;的右子树将被构建为
     <code>
      Construct([A[i+1], A[i+2], ..., A[A.length - 1]])
     </code>
    </li>
    <li>
     返回&nbsp;
     <code>
      root
     </code>
    </li>
   </ul>
   <p>
    请注意，我们没有直接给定&nbsp;A，只有一个根节点&nbsp;
    <code>
     root = Construct(A)
    </code>
    .
   </p>
   <p>
    假设
    <code>
     B
    </code>
    是
    <code>
     A
    </code>
    的副本，并附加值
    <code>
     val
    </code>
    。保证
    <code>
     B
    </code>
    &nbsp;中的值是不同的。
   </p>
   <p>
    返回&nbsp;
    <code>
     Construct(B)
    </code>
    。
   </p>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     示例 1：
    </strong>
   </p>
   <p>
    <strong>
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-1-1.png" style="height: 160px; width: 159px;">
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-1-2.png" style="height: 160px; width: 169px;">
    </strong>
   </p>
   <pre><strong>输入：</strong>root = [4,1,3,null,null,2], val = 5
<strong>输出：</strong>[5,4,null,1,3,null,null,2]
<strong>解释：</strong>A = [1,4,2,3], B = [1,4,2,3,5]
</pre>
   <p>
    <strong>
     示例 2：
     <br>
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-2-1.png" style="height: 160px; width: 180px;">
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-2-2.png" style="height: 160px; width: 214px;">
    </strong>
   </p>
   <pre><strong>输入：</strong>root = [5,2,4,null,1], val = 3
<strong>输出：</strong>[5,2,4,null,1,null,3]
<strong>解释：</strong>A = [2,1,5,4], B = [2,1,5,4,3]
</pre>
   <p>
    <strong>
     示例 3：
     <br>
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-3-1.png" style="height: 160px; width: 180px;">
     <img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/02/23/maximum-binary-tree-3-2.png" style="height: 160px; width: 201px;">
    </strong>
   </p>
   <pre><strong>输入：</strong>root = [5,2,3,null,1], val = 4
<strong>输出：</strong>[5,2,4,null,1,3]
<strong>解释：</strong>A = [2,1,5,3], B = [2,1,5,3,4]
</pre>
   <p>
    &nbsp;
   </p>
   <p>
    <strong>
     提示：
    </strong>
   </p>
   <ol>
    <li>
     <code>
      1 &lt;= B.length &lt;= 100
     </code>
    </li>
   </ol>
   <p>
    &nbsp;
   </p>
   <p>
    &nbsp;
   </p>
  </div>
 </body>
</html>